583. Простые множители

Любое натуральное число n можно разложить на простые множители, то есть представить в виде

n = f₁ * f₂ * … * f_k, где f_i > 1 и f_i £ f_j при i < j

Вход. Состоит из последовательности чисел. Каждая строка содержит число n (-2³² < n < 2³²), n ¹ ±1. Признак конца входных данных n = 0.

Выход. Для каждого входного n вывести его разложение на простые множители. Если n > 0, то разложение вывести в виде

n = f₁ x f₂ x … x f_k

При n < 0 разложение выводить в виде

n = -1 x f₁ x f₂ x … x f_k

Пример входа

-190
-191
-192
-193
-194
195
196
197
198
199
200
0
 

Пример выхода

-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5
 

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

Если входное значение n отрицательно, то печатаем делитель -1, и раскладываем на множители модуль числа n. Перебираем все возможные натуральные делители числа n. Для ускорения перебора выделим сначала делители - двойки. После этого достаточно перебирать лишь нечетные числа: 3, 5, 7, 9, … . Обнаружив делитель d, делим n на d, тем самым сокращая перебор. Если исходное число n содержало делитель, больший , то после выполнения цикла перебора нечетных делителей этот делитель останется в переменной n.

Пример

Пусть n = -194. Число n отрицательно, выводим -1, присваиваем n = 194. Выделяем двойки - делители: 194 = 2 * 97. Далее ищем делители числа 97, перебирая 3, 5, 7, 9 = . Среди этих чисел делителей 97 не находим. Следовательно 97 является делителем числа 194, большим = 13.

Реализация алгоритма

Читаем входное значение n, выводим его и знак равенства после него.

while(scanf("%d",&n), n != 0)

{

printf("%d = ",n);

Если n отрицательно, то выводим множитель –1 и знак умножения «х» после него.

if (n < 0)

{

printf("-1 x "); n = -n;

}

Отдельно обрабатываем двойки - делители.

while(n % 2 == 0)

{

if (n > 2) printf("2 x "); else printf("2\n");

n /= 2;

}

Перебираем все натуральные нечетные числа от 3 до . Проверяем, являются ли они делителями входного числа n. Выводим каждый найденный делитель.

// for(i = 3; i * i <= n; i += 2) will be Time Limit

for(i = 3; i <= (int)sqrt((double)n); i += 2)

{

while(n % i == 0)

{

if (n > i) printf("%d x ",i); else printf("%d\n",i);

n /= i;

}

}

Если n > 1, то n содержит последний простой делитель входного числа.

if (n > 1) printf("%d\n",n);

}